5. 最长回文子串

5. 最长回文子串

动态规划很多时候就是在填表

  1. 暴力解法
  2. 动态规划
  3. 马拉车算法,没仔细看

动态规划算法:

func longestPalindrome(s string) string {
    return dynamic(s)    
}

func dynamic(s string) string {

    dp := make([][]bool, len(s))

    for i := range dp {
        dp[i] = make([]bool, len(s))
        dp[i][i] = true
    }

    ret := s[0:1]
    mxLen := 1
    for j := 1; j < len(s); j++ {
        for i := 0; i<j; i++ {
            if s[i] == s[j] {
                if j-i < 3 {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i+1][j-1]
                }
                if dp[i][j] && j-i+1 > mxLen {
                    mxLen = j-i+1
                    ret = s[i:j+1]
                }
            } else {
                dp[i][j] = false
            }
        }
    }

    return ret
}

初始化:

填表格,对角线,也就是 i=j 时,单个字符,都是回文串,设置为 true dp[i][i] = true

遍历顺序:

因为初始化的是对角线,也就是如图所示:
图中对角线坐标写错了,应该是 [0,0] [1,1] [2,2] [3,3]
截屏 2024-09-11 23.48.54.png
如果按照平常的顺序,这么写代码遍历

for i := 0; i < len(s); i++ {
	for j := i+1; j<len(s); j++ {
		...
	}
}

那么会有如图所示的问题,[0,3] 会因为需要 [1,2] 的结果从而导致无法推算出正确的结果

截屏 2024-09-11 23.52.06.png

所以需要这么遍历,就能够使用到上一列的数据
截屏 2024-09-11 23.56.01.png


本站总访问量次 本站访客数人次 本文总阅读量